%%This is a very basic article template.
%%There is just one section and two subsections.
\documentclass[a4paper, 12pt]{scrartcl}

\usepackage[ngerman]{babel}
\usepackage[utf8]{inputenc}
\usepackage[babel,german=quotes]{csquotes}
\usepackage{graphicx}
\usepackage{fancyheadings}
\usepackage{listings}

\usepackage[colorlinks=true,linkcolor=black]{hyperref} %verweise

\usepackage{nomencl} %glossar
%\renewcommand{\nomname}{Glossar}
\makenomenclature

\pagestyle{fancy} 
\renewcommand{\nomname}{Glossar}
\newcommand{\oo}{\texttt{O(1)-Scheduler}}
\newcommand{\cfs}{\texttt{Completely Fair Scheduler}}

\setlength{\parindent}{0pt}	%Einrückung
\setlength{\parskip}{5pt}	%Absatzabstand

\title{Scheduling unter Linux}
\author{Michael Skinder}
\begin{document}
\maketitle
\thispagestyle{empty}

\begin{figure}[htbp]
\begin{center}
\includegraphics[height=120mm]{Bilder/scheduling.jpg} % www.4intranets.com
\label{Sechuling www.4intranets.com}   
\end{center}
\end{figure}

\newpage
\tableofcontents
\thispagestyle{empty}
\newpage
\setcounter{page}{1}


\section{Einleitung}
Ein wichtiger Aspekt jedes Betriebssystems ist der Scheduler. Er wählt Prozesse
aus, welche ausgeführt werden sollen. Dabei sind neben der Auswahl, welcher
Prozess als nächstes die CPU nutzen, darf viele weitere Aspekte wichtig. Es
sollen verschiedene Ziele erreicht werden, welche sich zum Teil gegenseitig
ausschließen oder zumindest behindern.\\
So soll ein hoher Durchsatz erreicht werden und die CPU dabei nie in den
Leerlauf kommen, aber dennoch das Ansprechverhalten der Programme sehr schnell
sein. Aus diesem Grund stehen kurze Zeitscheiben, mit einer hohen Rate an
Kontextwechseln, langen Zeitscheiben gegenüber, welche diesen Balast
reduzieren.

Zudem ist der Scheduler eine sehr häufig genutzte Komponente des
Betriebssystems. So wird bei jedem Prozesswechsel der Scheduler aufgerufen,
welcher nun den nächsten Prozess auswählen soll. Dies geschieht gut und gerne 50
mal in der Sekunde. Würde der Scheduler sehr lange für seine Entscheidung
brauchen, würde durch ihn und den Kontextwechsel viel Zeit damit
verbracht Prozesse zu wechseln. Diese Zeit ist für die verschiedenen Prozesse
verloren und der einzelne Prozess erreicht in der gleichen Zeit einen geringeren
Fortschritt.

Um einen guten Kompromiss zwischen den verschiedenen Zielen zu erreichen und den
Bedürfnissen verschiedenster Benutzer gerecht zu werden wurde in kurzer Zeit
gleich zwei Mal der Scheduler des Linux-Kernels gravierend verändert.\\
Auf diese Veränderungen und die Funktionsweise möchte ich im Folgenden eingehen.
Es soll klar werden warum diese Veränderungen nötig waren. Aus diesem Grund
möchte ich auf die grundlegende Funktionsweise des \oo{} und des \cfs{} eingehen.
Zum Abschluss soll eine kurze Gegenüberstellung verdeutlichen was beide
Scheduler leisten.

\vspace{15pt}
\textbf{Anmerkung}\\
Im folgenden Dokument sollen weitgehend die deutschen Bezeichnungen verwendet
werden. Bei Begriffen, die es im Deutschen nicht gibt oder die in der
Übersetzung zu befremdlich klingen, wird jedoch der Englische verwendet. Dies
soll das Lesen erleichtern und zum Verständnis beitragen.

\newpage
\section{Vergangenheit des Schedulers}
In diesem kurzen Kapitel möchte ich kurz auf die Eigenschaften der in der
Vergangenheit genutzten Scheduler eingehen und warum es notwendig war Neuerungen
einzuführen. Es wird kurz geschildert, was sie in der Lage waren zu leisten und
was nicht. Dadurch lässt sich die Entwicklung des Schedulers von Linux
nachvollziehen.

\subsection{Linux-Kernel 1.0}
In dieser Version des Linux-Kernels musste der Scheduler mit einfachen
Datenstrukturen arbeiten. Es standen lediglich prioritätssortierte Arrays mit
Listen zur Verfügung. Die einzelnen Prozesse wurden nach ihrer Priorität
einsortiert und ausgewählt. Die meisten Operationen benötigten eine Zeit von
O(n), was für eine größere Anzahl an Prozessen gänzlich ungeeignet ist.

\subsection{Linux-Kernel 2.0}
Diese Version von Linux wurde um SMP\footnote{Symmetrisches
Multiprozessorsystem}-Unterstützung ergänzt. Damit veränderte sich der Scheduler
grundlegend. Es wurden drei verschiedene Algorithmen für das Scheduling
implementiert, um allen Anforderungen gerecht zu werden.
Es gab jedoch nur eine Warteschlange, in der alle Prozesse einsortiert wurden.
So benötigten alle Operationen O(n) und es war nicht möglich die Prozesse an einen
Prozessor zu binden.

\subsection{Linux-Kernel 2.6}
Ab diesem Kernel wurde ein komplett neuer Scheduler verwendet. Es handelt sich
hierbei um den \oo{}. Seinen Namen verdankt er der Tatsache,
dass er einen neuen Prozess in konstanter Zeit auswählen kann um ihm die CPU
zuzuteilen. Von ihm wurde sich eine bessere SMP-Unterstützung und eine bessere
Skalierbarkeit bei steigender Anzahl an Prozessen versprochen. Selbst bei einer
geringen Anzahl an Prozessen erledigte er seine Arbeit schneller als der
Scheduler, der ab Kernel 2.0 verwendet wurde.

\subsection{Linux-Kernel 2.6.23}
Da es mit dem \oo{} schwer war ein gerechtes Scheduling durchzuführen, viele
Heuristiken\footnote{Heuristik; Die Kunst, mit begrenztem Wissen und wenig Zeit
zu guten Lösungen zu kommen} notwendig waren und es nicht einfach war die
CPU-Zeit geeignet aufzuteilen wurde ein neuer Scheuler entwickelt.\\
Der \cfs{} sollte diese Probleme beseitigen. So wurde ein Scheduler entwickelt,
welcher ohne Heuristiken und mit einfachen Algorithmen ein \enquote{faires}
Scheduling ermöglicht. Zudem ist der neue Scheduler einfacher zu erweitern.

\newpage
\section{O(1)-Scheduler}
Dieser Scheduler wurde sehr aufwendig gestaltet um die ihm gestellten Aufgaben
zu bewältigen. Er soll mit Heuristiken eine besonders gute Auswahl für den als nächstes
ausgeführten Prozess treffen. Im Folgenden möchte ich nun erläutern wie der \oo{} 
diese Entscheidungen trifft und welche Datenstrukturen er hierfür benötigt.

Die Richtlinien des \oo{} ist so ausgelegt, dass Prozesse
bevorzugt werden, welche viel damit beschäftigt sind Ein - und Ausgaben zu
machen. Damit wird erreicht, dass eine gute Reaktionszeit erzielt wird und der
Nutzer flüssig arbeiten kann. Prozessen, welche fast ausschließlich die CPU
nutzen, wird im Gegensatz nicht so häufig die CPU zugeteilt, da sie keinen
Einfluss darauf haben, ob das System als \enquote{flüssig} wahrgenommen wird.
Dies liegt daran, dass diese Programme nicht mit dem Benutzer interagieren. Sie
bekommen statt dessen länger die CPU und werden so weniger durch Kontextwechsel
beeinflusst.\\
Im Folgenden wird nun beschrieben, wie die Ziele der Richtlinien
verwirklicht werden.


\subsection{O(1)-Scheduling}

Im Gegensatz zu früheren Schedulern wurde die Datenstruktur zur Verwaltung der
Prozesse erweitert. Es existiert nun nicht nur eine Datenstruktur um die
Prozesse zu verwalten sondern zwei. Diese ist schematisch in Abbildung
\ref{Warteschlange} dargestellt. Es existiert ein Array für die Prozesse, welche
ihre Prozessorzeit bereits verbraucht haben und eines für die anderen Prozesse.
Hat ein Prozess aus dem aktiven Array seine Zeit verbraucht wird er in das
abgelaufene Array verschoben.\\ 
\begin{figure}[htbp]
	\centering
	\includegraphics[height=70mm]{Bilder/o_von_1_runqueue.png}
	\caption{Warteschlange}
	\label{Warteschlange}
\end{figure}
In jedem dieser Arrays gibt es für jede Priorität einen Eintrag. Dort ist ein
Verweis auf eine Liste in der dann die einzelnen Prozesse stehen. Da es nur
konstant viele Prioritäten gibt erfolgt die Suche nach dem Prozess mit der
höchsten Priorität in O(1). Außerdem gibt es für diese Suchen einen speziell
optimierten Algorithmus, der diese beschleunigt. Dieser Algorithmus nutzt die
in Abbildung \ref{Warteschlange} dargestellte Bitmap. In ihr ist ein Bit für
jede Priorität. Existiert ein lauffähiger Prozess einer Prioritätsklasse wird
das zugehörige Bit gesetzt. So kann sehr schnell der nächste auszuwählende
Prozess gefunden werden.\\
Gibt es mehrere Prozesse mit der gleichen Priorität bekommen diese nach einem
weiteren Schedulingverfahren die CPU zugeteilt. Hierfür wird ein Round-Robin
genutzt.\\
Sollte sich im aktiv Array kein Prozess mehr befinden werden beide Arrays
einfach getauscht. So ist es in kürzester Zeit möglich eine frisch gefüllte
Warteschlange zur Verfügung zu haben. Hierbei werden lediglich zwei Zeiger
getauscht. Dies stellt die Zeitscheibenberechnung dar, welche früher durch
Iterieren durch die Prozesslisten und somit in O(n) erfolgte. Nun ist die
Zeitscheibenneuberechnung in O(1) möglich.


\subsection{Berechnung von Prioritäten und Zeitscheiben}
Um die Position eines Prozesses in den Arrays und die Länge der Zeitscheiben zu
berechnen werden verschiedene Angaben benötigt, welche der Benutzer nur
teilweise beeinflussen kann.\\ Für die Priorität eines Prozesses sind zwei
Faktoren wichtig. Zum einen der \enquote{nice-Wert} welcher eine statische
Priorität darstellt. Zu dieser statischen Priorität kommt ein Bonus hinzu der
sich an Hand der \enquote{Interaktivität} berechnet. Dies spiegelt wieder, dass
ein - und ausgabeintensive Prozesse bevorzugt werden.\\
Um festzustellen, welcher Prozess interaktiv ist wird die Zeit gemessen, in der
ein Prozess schläft. Ein Prozess kann auf seine Priorität maximal einen Bonus
oder eine Strafe von fünf Prioritätsstufen bekommen. Prozesse die fast
ausschließlich schlafen da sie auf Ein - und Ausgaben warten werden so belohnt.
Genauso schnell wie ein Prozess diesen Bonus bekommen hat kann er ihn aber auch
wieder verlieren. Braucht ein Prozess ständig seine Zeitscheibe auf und
schläft somit nicht, bekommt er seinen Bonus weggenommen und sogar eine
Strafe. \\ 
Es gibt außerdem eine weitere Möglichkeit interaktive Prozesse zu belohnen.
Stellt sich heraus, dass ein Prozess sehr interaktiv ist wird er nicht
aus dem aktiv Array entfernt wenn seine CPU-Zeit abgelaufen ist. Dies wird durch
den nice-Wert und den Bonus festgelegt. Ein Prozess mit dem nice-Wert -20
müsste schon sehr viel CPU-Zeit beanspruchen dass er nicht wieder in das
aktiv Array eingefügt wird. Hingegen ist es für einen Prozess mit dem
nice-Wert +19 quasi unmöglich erneut eingefügt zu werden. Zudem besteht die
Möglichkeit Prozesse wieder in das aktiv Array aufzunehmen. Dies kann geschehen
wenn sich ein Prozess im abgelaufen Array befindet und wieder lauffähig wird.\\
Durch das Wiedereinfügen von Prozessen wird jedoch der Wechsel der beiden Arrays
verzögert. Deswegen muss immer geprüft werden ob es einen Prozess gibt der
gerade am Verhungern ist.

Die Zeitscheibe eines Prozesses zu berechnen ist wesentlich einfacher. Sie
orientiert sich lediglich an dem \enquote{nice-Wert}, also der statischen
Priorität. Hierbei sind Zeiten zwischen 5ms und 800ms möglich. So bekommt ein
Prozess mit der maximalen Priorität, also dem nice-Wert -20 eine Zeitscheibe
von 800ms. Ist der nice-Wert hingegen bei +19 bekommt der Prozess lediglich
eine Zeitscheibe von 5ms.\\ 
Zwar benötigen interaktive Prozesse keine großen Zeitscheiben, jedoch
profitieren sie davon, da der Rest der Zeitscheibe nicht verfällt. Verbraucht
ein Prozess also nur die Hälfte seiner Prozessorzeit und wartet auf eine Ein -
oder Ausgabe kann er die restliche Zeit nutzen sobald diese erfolgt ist.\\
Wird ein neuer Prozess erzeugt teilen sich der Eltern - und Kindprozess die
verbleibende Zeit. Dies soll verhindern, dass sich durch das Erzeugen von
Kindprozessen ein größerer Zeitscheibe erschlichen wird. Sollten die
Zeitscheiben jedoch nicht mehr ausreichend sein, also nur noch Zeit mit
Kontextwechseln verbraucht wird, wird dieser an Hand der Priorität für die
einzelnen Prozesse erneut berechnet.

\subsection{SMP-Unterstützung}
Um im Vergleich zu vorigen Schedulern ein besseres Verhalten auf SMP-Systemen zu
erreichen gibt es im \oo{} für jeden Prozessor eine eigene Datenstruktur
(Runqueue) welche die Prozesse speichert. Aus diesem Grund läuft ein Prozess
immer nur auf dem selben Prozessor. Legt sich also ein Prozess schlafen und gibt
einem Anderen die Möglichkeit die CPU zu nutzen wird ein Kontextwechsel
ausgeführt und die Variablen des anderen Prozesses geladen. Daten die jedoch im
Cache zwischengespeichert sind werden nicht verändert. Brauch der andere Prozess
nicht den gesammten Cache verbleiben von vorheringen Prozessen Daten zurück die
später genutzt werden können. Dadurch, dass ein Prozess auf einem Prozessor
gehalten wird, befinden sich sehr wahrscheinlich noch Daten im Cache und müssen
nicht vom Hauptspeicher oder gar der Festplatte geladen werden. Dies spart
enorm Zeit, da die Geschwindigkeit moderner Prozessoren die des Hauptspeichers
bei weitem übertrifft.\\
Nur wenn in den einzelnen Runqueues ein extremer Unterschied in der Anzahl der
Prozesse besteht wird ein Ausgleich vorgenommen. Dieser Ausgleich wird immer
gestartet wenn es eine leere Runqueue gibt oder das System im Idle-Zustand ist.
Außerdem wird alle 200ms geprüft ob es ein Ungleichgewicht zwischen den
Runqueues gibt.\\
Einer Runque werden nur Prozesse entzogen, wenn diese mehr als 25\% mehr
Prozesse hat als die aktuell Betrachtete. Ist eine solche Runqueue gefunden geht
es an die Auswahl der Prozesse, welche zu verschieben sind.\\
Hierbei werden Prozesse bevorzugt welche bereits ihre Zeitscheibe aufgebraucht
haben und somit im abgelaufenen Array sind. Diese haben mit einer höheren
Wahrscheinlichkeit keine Daten mehr im Cache und so spielt es für sie keine
Rolle ob sie auf dem aktuellen Prozessor oder einem Anderen laufen. Des weiteren
werden Prozesse mit einer höheren Priorität bevorzugt ausgewählt. Ist ein
passender Kandidat gefunden wird er in eine der leereren Runqueues eingefügt.

\subsection{Steigerung der Interaktivität}
Eine weitere wichtige Neuerung kam mit dem \oo{} zu Linux hinzu. So wurde der
Kernel präemptiv. Die meisten Kernelfunktionen können in ihrer Ausführung nun
unterbrochen werden. Dies gewährleistet eine geringere Latenz für Prozesse wenn
der Kernel gerade langwierige Aufgaben erledigt. Allerdings existieren
Kernelfunktionen die atomar ausgeführt werden müssen und aus diesem Grund nicht
unterbrechbar sind.


\newpage
\section{Completely Fair Scheduler}
Der \cfs{} verfolgt im Gegensatz zum \oo{} eine einfachere Strategie. Es werden
keine aufwändigen Heuristiken verwendet, sondern ein einfaches Kriterium für die
Auswahl eines Prozesses genutzt. Es wird der Prozess ausgewählt, der am längsten
warten musste. Diese werden in einem Rot-Schwarz-Baum gespeichert und so kann in
O(log(n)) der nächste Prozess ausgesucht werden. Prozesse welche eine sehr hohe
Wartezeit haben befinden sich im Rot-Schwarz-Baum weit links und werden
demnächst ausgewählt. Um die Zugriffszeiten zu verkürzen existiert ein Zeiger
auf den als nächstes auszuwählenden Prozess.\\ Auch bei dieser
Einplanungsstrategie werden indirekt Prozesse bevorzugt, welche viel auf Ein -
und Ausgaben warten müssen was. Dies wird beim Weiterlesen klar werden.

Auch in einer weiteren Hinsicht ist der \cfs{} einzigartig. Denn er verwendet
keine Zeitscheiben die ein Prozess aufbrauchen kann. Viel mehr gibt es
global eine Zeit, die angibt in welcher Zeit jeder Prozess einmal die CPU
zugeteilt bekommen sollte.

Im Folgenden wird nun beschrieben, wie der \cfs{} seine Aufgaben erledigt.

\subsection{Berechnung der Wartezeit}
Da jeder Prozess nach seiner Wartezeit ausgewählt wird ist die Berechnung ein
wichtiger Aspekt des \cfs{}. Es wird hierbei nicht einfach nur die Zeit
gemessen, in der ein Prozess bereit zur Ausführung ist aber nicht zur
Ausführung kommt. Viel mehr wird dies in Abhängigkeit von den anderen Prozessen
berechnet. Sollen n Prozesse auf einem Prozessor laufen, so sollte jeder
Prozess 1\textbackslash{}n der CPU-Zeit bekommen. Deshalb wird dem Prozess nach
m Sekunden nur eine Wartezeit vom m\textbackslash n Sekunden gutgeschrieben und
keine m.

Bekommt ein nun Prozess die CPU wird die Rechenzeit von der Wartezeit abgezogen.
Aus diesem Grund ist nach einem neuen Aufruf des Schedulers, in dem die
Statistiken aktualisiert werden, die Wartezeit des Prozesses gesunken. Dies
führt dazu, dass der Prozess an einer weiter rechts liegenden Stelle im
Rot-Schwarz-Baum wieder eingefügt wird. Somit hat ein anderer Prozess die linke
Position im Rot-Schwarz-Baum und wird als nächstes ausgewählt werden.

Dies bevorzugt indirekt Prozesse welche hauptsächlich mit Ein - und Ausgaben
beschäftigt sind. Denn diese benötigen immer nur sehr wenig CPU-Zeit und
bekommen von ihrer Wartezeit auch nur wenig abgezogen wenn sie sich wieder
schlafen legen. So wandern sie im Rot-Schwarz-Baum nicht in Positionen in denen
sie nicht schnell wieder ausgewählt werden.

\subsubsection{Umgang mit Prioritäten}
Da es auf einem Computer Prozesse sind die wichtiger als Andere sind muss ein
Scheduler diese auch bevorzugen, so dass Zeitanforderungen eingehalten werden
können. So soll ein Batchprozess keinen Prozess verdrängen, der die Eingaben
eines Benutzers verarbeitet, da dies den Eindruck erweckt das System würde
nicht flüssig laufen.

Aus diesem Grund gestaltet sich die Berechnung der Wartezeit eines Prozesses
etwas komplizierter. Es wird mit Gewichtungen gearbeitet und aus diesen dann die
Wartezeit berechnet. Die Gewichtung kann an Hand des nice-Wertes abgelesen
werden. Diese sind so gewählt, dass eine Erhöhung des Werts eines Prozesses 10\%
weniger CPU-Zeit bedeuten.
\begin{center}
\lstset{language=c++}
\lstinputlisting[]{Skripte/Last.cpp}
\end{center}
Für jeden Prozess wird nun auch seine Gewichtung gespeichert, welche einfach an
Hand des nice-Wertes abgelesen werden kann. Mit dessen Hilfe und der
Realtime-Clock lässt sich nun die vergangene gewichtete Rechenzeit berechnen.
Hierfür teilt man die Gewichtung eines Prozesses mit dem nice-Wert 0
(NICE\_0\_LOAD) durch die Gewichtung des gerade betrachteten Prozesses
(curr-$>$load.weight) und multipliziert diese mit der realen vergangenen Zeit
(delta\_exec). Dieser Wert kann nun von der angesammelten Wartezeit abgezogen
werden.

\begin{center}
$delta\_exec\_weighted=delta\_exec*\frac{NICE\_0\_LOAD}{curr->load.weight}$
\end{center}

Da mit steigender Priorität (also sinkendem nice-Wert) die Gewichtung des
Prozesses zunimmt wird einem Prozess mit höhere Priorität weniger seiner
realen Rechenzeit von der Wartezeit abgezogen. Dies sorgt dafür, dass der
Prozess im Rot-Schwarz-Baum nicht so weit rechts einsortiert wird. Er kann somit
nach einer kürzeren Wartezeit wieder an die CPU gelangen.

Bei Echtzeitprozessen\footnote{Es wird jedoch keine harte Echtzeit garantiert}
gestaltet sich das Ganze wiederum etwas anders. Diese werden nicht wie die
gewöhnlichen Prozesse in einem Rot-Schwar-Baum verwaltet sondern erhalten eine
eigene Datenstruktur. Diese ist als Prioritätsarray organisiert. \begin{figure}[htbp]
	\centering
	\includegraphics[height=40mm]{Bilder/echtzeitprozesse.png}
	\caption{Echtzeitprozesse}
	\label{Echtzeitprozesse}
\end{figure} 
Prozesse mit der gleichen Priorität befinden sich in einem Eintrag im Array und
werden durch eine verkettete Liste verwaltet.\\
Wird nun ein Echtzeitprozess lauffähig darf dieser in jedem Fall die CPU
benutzen. Sie werden somit jedem normalem Prozess im Rot-Schwarz-Baum
vorgezogen. Die einzige Ausnahme stellt hierbei ein Echtzeitprozess mit einer
höheren Priorität dar. Dieser wird natürlich bevorzugt und darf den anderen
Prozess auch unterbrechen.\\ 
Existieren nun mehrere Echtzeitprozesse können diese auf zwei verschiedene Arten
eingeplant werden. Zum einem können sie nach einem \enquote{Round Robin} mit
Zeitscheiben eingeplant werden. Hierbei müssen sich Prozesse mit gleicher
Priorität die CPU teilen und werden unterbrochen wenn ihre Zeitscheibe
abgelaufen ist. Eine weitere Möglichkeit besteht darin die Prozesse mit einem
\enquote{FIFO-Algorithmus} einzuplanen. Bei dieser Variante darf ein
Echtzeitprozess so lange laufen bis er die CPU freiwillig wieder abgibt. Es
versteht sich von selbst, dass ein schlecht geschriebenes Programm auf diese Art
den ganzen Computer blockieren kann.

\subsubsection{Dauer der Ausführung}
Da es beim \cfs{} keine Zeitscheiben gibt muss ein anderes Kriterium genutzt
werden um festzustellen, wie lang ein Prozess die CPU nutzen darf. Wird die CPU-Zeit zu
groß gewählt ist es nicht möglich eine angemessene Reaktionszeit zu garantieren.
Ist diese jedoch zu klein wird ein Großteil der Rechenzeit mit Kontextwechseln
verschwendet.\\
Aus diesem Grund wird in periodischen Zeitabständen geprüft ob es notwendig ist
einem neuen Prozess die CPU zuzuteilen. Diese Zeitabstände sind nicht fix. Sie
ändern sich mit der Last des Systems. Als Standardwert ist jedoch festgelegt,
dass jeder lauffähige Prozess innerhalb von 20ms einmal zur Ausführung kommen
sollte. Übersteigt die Anzahl der lauffähigen Prozesse eine festgelegte Grenze
wird die Zeit, in der jeder lauffähige Prozess einmal zur Ausführung kommen
soll, linear angehoben.\\
Anhand dieser Werte wird entschieden wann geprüft werden muss, ob ein anderer
Prozess die CPU zugeteilt bekommen soll.

Wurde zwar die Zuteilung der CPU überprüft aber befunden, dass der aktuelle
Prozess die CPU weiterhin nutzen soll werden noch die Statistiken über die
Prozesse erneuert. So wird zum Beispiel die Wartezeit der Prozesse auf einen
aktuelleren Stand gebracht.

\subsection{SMP-Unterstützung}
Um eine gute Unterstützung für SMP-Systeme zu gewährleisten wurden einige
Richtlinien implementiert, die dies gewährleisten sollen.\\
Eine Warteschlange pro Prozessor gewährleisten, dass ein Prozess auf
dem Prozessor ausgeführt wird auf dem er gestartet wurde. Dies stellt sicher, dass
möglichst viele Daten noch im Prozessorcache vorhanden sind und nicht aus dem
Speicher geladen werden müssen. \\
Eine geschickte Lastverteilung unter den Prozessoren sorgt zudem dafür,
dass das System gleichmäßig ausgelastet wird. So wird gleich bei der Erzeugung
eines Prozesses geprüft auf welchem Prozessor er ausgeführt werden soll. Da ein
noch nie gestarteter Prozess auch keine Daten geladen hat ist dies genau die
richtige Zeit dafür.\\
Zwar ist es auch möglich, dass ein Prozess auf einen anderen Prozessor
verschoben wird. Doch wird dies nur gemacht wenn die einzelnen Prozessoren sehr
unterschiedliche Lasten haben.\\
Prozessorgruppen sorgen zudem dafür, dass ein Prozess nur auf den für
ihn geeigneten Prozessor verschoben wird. So wird beachtet welche Prozessoren
beieinander liegen und sich zum Beispiel einen Cachespeicher teilen. Prozesse
werden natürlich vorrangig auf Prozessoren verschoben bei dem sich die
nachteiligen Auswirkungen besonders wenig auswirken.

\subsection{Gruppenverwaltung}
In der Version 26.6.24 bekam der \cfs{} eine weitere Verbesserung. Es wurde ein
gruppenweises Prozesseinplanen implementiert. Es wurde so möglich, dass erst
eine bestimmte Gruppe von Prozessen fair ausgewählt wurde in welcher dann
wiederum jeder Prozess fair eingeplant wurde. Dies verbesserte besonders das
Verhalten des Systems wenn es im Mehrbenutzerbetrieb genutzt wurde. Gab es
früher einen Benutzer A mit vier Prozessen und einen Benutzer B mit nur einem
Prozess bekam jeder Prozess ein Fünftel der Prozessorzeit. Somit standen
Benutzer B nur 20\% der CPU zur Verfügung. Durch das gruppenweise Einplanen
bekommt jeder Benutzer zunächst eine Hälfte der Prozessorzeit in welcher
wiederum die einzelnen Prozesse eingeplant werden.

\subsection{Erweiterbarkeit}
Aus der normalen Gruppenverwaltung lässt sich ein weiteres Feature erreichen.
Der Scheduler kann hierdurch nämlich erweitert werden. Es werden nich wie im
üblichen Sinne Module geladen, sondern Gruppen mit eigenen Richtlinien erstellt
welche dann eingeplant werden. So ist es einfach möglich eine etwas abgewandelte
Strategie für das Scheduling zu erreichen.

\subsection{Steigerung der Interaktivität}
Auch der \cfs{} profitiert wie der \oo{} von einem präemptiven Kernel. So sind
auch hier Aufgaben des Kernel Unterbrechbar. Hierdurch kann schneller auf
Anfragen an wichtige Prozesse geantwortet werden und somit die Latenz gesenkt
werden. Allerdings sind wie beim \oo{} nicht alle Aufrufe des Kernels
unterbrechbar. Einige atomar auszuführenden Funktionen werden wohl immer
vorhanden sein.

\newpage
\section{Vergleich}
Nun, da die Funktionsweise des \oo{} und des \cfs{} bekannt sind, ist es an
der Zeit zu betrachten, wo die Stärken und Schwächen der einzelnen Verfahren
liegen. Sicher ist jedoch, dass beide innovativ sind und die an sie gestellten
Aufgaben bewältigen können.

Gerade der \oo{} hat eine enorme Steigerung der Leistungsfähigkeit mit sich
gebracht, da er Scheduler ablöste welche in O(1) ihre Entscheidungen trafen.
Jedoch nutzt er hierfür aufwändige Heuristiken, welche sehr oft ausgeführt
werden müssen, da der Scheduler die meist ausgeführten Codezeilen im Kernel
enthält. \\ 
Der \cfs{} braucht zwar O(log(n)) um seine Aufgaben zu erledigen,
nutzt dabei jedoch einfachste Berechnungen, welche schnell auszuführen sind.
Somit dürfte der Scheduler welcher seit der Kernel Version 2.6.24 enthalten ist
seine Arbeit bei geringer bis mäßiger Prozessanzahl schneller erledigen als der
\oo{}.

Beide Scheduler verfolgen die gleichen Richtlinien wenn es darum geht welche
Prozesse bevorzugt auszuwählen sind. Jedoch wird beim \oo{} aktiv nachgeholfen um
dies zu bewerkstelligen und interaktive Prozesse mit einem Bonus belegt. Der
\cfs{} hingegen nutzt die Tatsache aus, dass E/A- lastige Prozesse wenig
Rechenzeit haben und somit wenig ihrer Wartezeit abgezogen bekommen. Somit sind
beim \cfs{} keine weiteren Berechnungen nötig und es wird Rechenzeit
eingespart.
Auch ist es unmöglich, dass beim \cfs{} ein Prozess verhungern kann. Dies muss
beim \oo{} wiederum aufwändig überwacht werden.

Ein weitere Pluspunkt des \cfs{} ist die leichte Erweiterbarkeit. Er kann mit
wenig Aufwand an spezielle Aufgabengebiete angepasst werden. Somit ist er
universeller einsetzbar.

Bei der Unterstützung von SMP-Systemen liegen beide Scheduler jedoch gleich auf.
Sie nutzen eine Warteschlange pro Prozessor und vertrauen auf ausgefeilte
Strategien zur Lastverteilung. Somit stellen sie sicher, dass moderne
Prozessoren optimal ausgelastet werden.

Abschließend kann man sagen, dass der \cfs{} dem \oo{} überlegen sein dürfte.
Dies ist jedoch am puren Vergleich der Implementierung schwer zu sagen. Hierfür
bedarf es Testläufe, in denen die Last vorher definiert ist und gemessen werden
kann wie sich das System bei zunehmender Anzahl an Prozessen verhält.
Interessant wäre hierbei festzustellen wie hoch der Ballast der jeweiligen
Scheduler ist und ab welcher Prozessanzahl der \oo{} dem \cfs{} überlegen ist.

Ein tatsächliches Argument, welches dafür spricht, dass der \cfs{} dem \oo{}
überlegen ist, ist dass beide Scheduler von Ingo Molnár entwickelt worden sind
und der \cfs{} später entstand. So wurde aus dem Vorgänger gelernt und ein
performanteres System entwickelt.
\newpage
\section*{Anhang}

\subsection*{Rot-Schwarz-Baum}
Ein Rot-Schwarz-Baum ist eine vom binäreren Suchbaum abgeleitete balancierte
Datenstruktur. Dadurch, dass der Baum balanciert ist werden Zugriffszeiten von
O(log(n)) garantiert. Alle Operationen funktionieren prinzipiell wie bei einem
normalen binären Baum. Die einzige Besonderheit sind die vorgeschriebenen
Eigenschaften, welcher ein Rot-Schwarz-Baum erfüllen muss und welche die
Balanciertheit gewährleisten.

\begin{figure}[htbp]
	\centering
	\includegraphics[height=70mm]{Bilder/red-black_tree.png} %www.wikipedia.de
	\caption{Rot-Schwarz-Baum}
\end{figure}


\newpage
\begin{thebibliography}{99}
\bibitem{1} {Thomas Gleixner, \textsl{The Completly Fair
Scheduler}, Linuxfoundation Japan Symposium, Juli 2008}

\bibitem{2}{Robert Love, \textsl{Linux-Kernel-Handbuch - Leitfaden
zu Design und Implementierung von Kernel 2.6}, ADDISON-WESLEY, 2005}

\bibitem{3}{Daniel P. Bovet and Marco Cesati,
\textsl{Understanding the Linux Kernel}, O'Reilly, 2005}

\bibitem{4}{Abraham Silberschatz, \textsl{Operating System
Concepts}, Wiley, 209} 

\bibitem{5}{Robert Love, \textsl{Linux kernel development}, Sams,
2005}
\bibitem{6}{Wolfgang Mauerer, \textsl{Professional Linux Kernel Architecture},
Wrox, 2008 }

\bibitem{7}{Chandandeep Sin..., \textsl{Completely Fair Scheduler}, Linux
Journal, 2009}

\end{thebibliography}
\listoffigures 
   
\newpage 
\nomenclature{Gedöns}{Definition} 

\printnomenclature  
\end{document}
